// Created by WXX on 2021/12/14 21:19
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

/**
 * 执行用时：136 ms, 在所有 C++ 提交中击败了25.82%的用户
 * 内存消耗：12.9 MB, 在所有 C++ 提交中击败了60.66%的用户
 */
class Solution {
public:
    int longestStrChain(vector<string> &words) {
        sort(words.begin(), words.end(), [](string &a, string &b) {
            return a.size() < b.size();
        });

        int n = words.size();
        vector<int> f(n);
        int res = 0;
        for (int i = 0; i < n; i++) {
            f[i] = 1;
            for (int j = 0; j < i; j++)
                if (check(words[j], words[i]))
                    f[i] = max(f[i], f[j] + 1);
            res = max(res, f[i]);
        }
        return res;
    }

    bool check(string &a, string &b) {

        if (a.size() + 1 != b.size()) return false;

        int i = 0;
        for (auto c : b) {
            if (i < a.size() && a[i] == c)
                i++;
        }
        return i == a.size();
    }
};

int main() {

    vector<string> words = {"a", "b", "ba", "bca", "bda", "bdca"};
    cout << Solution().longestStrChain(words) << endl;  // 4

    return 0;
}
